#include "StdAfx.h"
#include "KMPAlgorithm.h"

KMPAlgorithm::KMPAlgorithm(void)
{
	allText="kxciawiaecnzkxcnvpiawiaehoqhierhgudhfb";
	matchString="iawiaeho";
	getNextArray();
	Match();
}

void KMPAlgorithm::getNextArray(){
	int matchStringLength = matchString.size();
	next[0] = -1;

	for(int i = 1;i<matchStringLength;i++){
		int lastPoi = i-1;
		while(true){
			if(lastPoi == -1){
				if(matchString.at(i) == matchString.at(0)){
					next[i] = 0;
				}else{
					next[i] = -1;
				}
				break;
			}
			int stringPoi = next[lastPoi];
			char nowChar = matchString.at(i);
			char matchChar = matchString.at(stringPoi+1);
		
			if(matchChar == nowChar){
				next[i] = stringPoi+1;
				break;
			}else{
				lastPoi = stringPoi;
			}
		}
	}
	PrintNext();
}

void KMPAlgorithm::Match(){
	int allSize = allText.size();
	int matchIndex = 0;
	int i = 0;
	for(i = 0;i<allSize;i++){
		
		if(allText.at(i) != matchString.at(matchIndex)){
			matchIndex = next[matchIndex]+1;
		}else{
			matchIndex++;
			if(matchIndex == matchString.size()){
				break;
			}
		}
	}

	cout<<"index="<<i-matchString.size()<<endl;
}

void KMPAlgorithm::PrintNext(){
	for(int i = 0;i<8;i++){
		cout<<next[i]<<'\t';
	}
	cout<<endl;
}

KMPAlgorithm::~KMPAlgorithm(void)
{
}


/**void main(){
	KMPAlgorithm testClass;
	
	cin>>testClass.matchString;
	cout<<"test="<<testClass.matchString.at(1)<<endl;

	string test = "sdfsdf";
	string &a = test;
	cout<<a<<" "<<&a<<" "<<&test<<endl;
	
}*/
